|
In mathematics, in the branch of combinatorics, a graded poset is a partially ordered set (poset) ''P'' equipped with a rank function ρ from ''P'' to N satisfying the following two properties: * The rank function is compatible with the ordering, meaning that for every ''x'' and ''y'' in the order with ''x'' < ''y'', it must be the case that ρ(''x'') < ρ(''y''), and * The rank is consistent with the covering relation of the ordering, meaning that for every ''x'' and ''y'' for which ''y'' covers ''x'', it must be the case that ρ(''y'') = ρ(''x'') + 1. The value of the rank function for an element of the poset is called its rank. Sometimes a graded poset is called a ranked poset but that phrase has other meanings; see ranked poset. A rank or rank level of a graded poset is the subset of all the elements of the poset that have a given rank value.〔.〕〔.〕 Graded posets play an important role in combinatorics and can be visualized by means of a Hasse diagram. == Examples == Some examples of graded posets (with the rank function in parentheses) are: * the natural numbers N, with their usual order (rank: the number itself), or some interval () of this poset, * N''n'', with the product order (sum of the coefficients), or a subposet of it that is a product of intervals, * the positive integers, ordered by divisibility (number of prime factors, counted with multiplicity), or a subposet of it formed by the divisors of a fixed ''N'', * the Boolean lattice of finite subsets of a set (number of elements of the subset), * the lattice of partitions of a set into finitely many parts, ordered by reverse refinement (number of parts), * the lattice of partitions of a finite set ''X'', ordered by refinement (number of elements of ''X'' minus number of parts), * a group and a generating set, or equivalently its Cayley graph, ordered by the weak or strong Bruhat order, and ranked by word length (length of shortest reduced word). * * In particular for Coxeter groups, for example permutations of a totally ordered ''n''-element set, with either the weak or strong Bruhat order (number of adjacent inversions), * geometric lattices, such as the lattice of subspaces of a vector space (dimension of the subspace), * the distributive lattice of finite lower sets of another poset (number of elements), * Young's lattice, a particular instance of the previous example (number of boxes in the Young diagram), * face lattices of convex polytopes (dimension of the face, plus one), * abstract polytopes ("distance" from the least face, minus one ), * abstract simplicial complexes (number of elements of the simplex). 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「Graded poset」の詳細全文を読む スポンサード リンク
|